package roman.algorithm;

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class CentroidClustering {
	
	static int [][] sim;
	static int problemSize;
	static int leastClusters = 5;
	// the biggest value can be represented by an int is 2147483647.
	static int multiplier = 2000000000;		
	// store the number of nodes in each set
	static HashMap<Integer,LinkedList<Integer>> nodeMap = new HashMap<Integer,LinkedList<Integer>>();
	static List<Node> nodeList = new ArrayList<Node>();
	static TreeMap<Integer,Edge> map = new TreeMap<Integer,Edge>();
	
	static class Node{
		int setName;
		Node parent;					// nodes with parent null is the name of the set
		public Node(int n, Node p){
			setName = n;
			parent = p;
		}
	}
	
	static class Edge{
		int fromNode;
		int toNode;
		public Edge(int a, int b){
			fromNode = a;
			toNode = b;
		}
	}
	
	public static int find(int i){
		if(nodeList.get(i).parent == null)
			return i;
		else{
			int tmp = find(nodeList.get(i).parent.setName);
			// in this application the path compression is not necessary
//			nodeList.get(i).parent = nodeList.get(tmp);
			return tmp;
		}
	}
	
	public static void updateSim(int a, int b){
		// first decide which node to be exclude from the independent set
		// then select the node to be the representative of the group
	
		// the mapping of all node is stored in nodemap
		// for all components in nodeMap.get(a) and nodeMap.get(b), find their similarity to the other elements
		// then combine the two linkedlist and set the selected element as key
		
		double maxSim = 0;
		LinkedList<Integer> tmpList = new LinkedList<Integer>();
		tmpList.addAll(nodeMap.get(a));
		tmpList.addAll(nodeMap.get(b));
		int centroid = tmpList.get(0);
		for(int i = 0; i < tmpList.size(); i++){
			double tmpSim = 0;
			for(int j = 0; j<tmpList.size(); j++){
				tmpSim += sim[tmpList.get(i)][tmpList.get(j)]/(double)multiplier;
			}
			if (tmpSim > maxSim){
				maxSim = tmpSim;
				centroid = tmpList.get(i);
			}
		}
		
		nodeMap.remove(a);
		nodeMap.remove(b);
		nodeMap.put(centroid,tmpList);
		
		for(int i = 0; i < problemSize; i++)
			if(sim[a][i] != 0)
				map.remove(sim[a][i]);
		
		for(int i = 0; i < problemSize; i++)
			if(sim[b][i] != 0)
				map.remove(sim[b][i]);
		
		for(int i : tmpList){
			if(i!=centroid)
				nodeList.get(i).parent = nodeList.get(centroid);
		}

		for(int i = 0; i < problemSize; i++){
			if(nodeMap.containsKey(i) && i!=centroid){
				insertNode(i,centroid);
			}
		}
	}

	public static void insertNode(int i, int j){
		if(sim[i][j] != 0){
			while(map.containsKey(sim[i][j])){
				sim[i][j] = sim[i][j]+1;
				sim[j][i] = sim[i][j];
			}
			map.put(sim[i][j], new Edge(i,j));
		}
	}
	
	public static void join(){
		if(map.size()==0)
			return;
		Edge tmpEdge = map.get(map.lastKey());
		int fromNode, toNode;
		fromNode = tmpEdge.fromNode;	// bigger one
		toNode = tmpEdge.toNode;		// smaller one
		updateSim(toNode,fromNode);
	}
	
	public static void process() throws Exception{
		problemSize = 25;
		HashMap<Integer,LinkedList<Integer>> results = new HashMap<Integer,LinkedList<Integer>>();
		Map<Integer, String> nameTable = new HashMap<Integer,String>();
		Set<String> baseSet = new HashSet<String>();
		
		readFile("dataAm25.in","artists25.in","artists25.in",nameTable,baseSet);
		LinkedList<Integer> tmpll;
		for(int i=0; i<problemSize; i++){
			nodeList.add(new Node(i,null));
			tmpll = new LinkedList<Integer>();
			tmpll.add(i);
			nodeMap.put(i, tmpll);
		}
		
		for(int i = 0; i < problemSize; i++)
			for(int j = 0; j < i; j++)
				insertNode(i, j);
		
		for(int i = 0; i<(problemSize - leastClusters); i++)
			join();
		
		int tmp;
		for(int i = 0; i<problemSize; i++){
			tmp = find(i);
			if(results.containsKey(tmp))
				results.get(tmp).add(i);
			else{
				results.put(tmp, new LinkedList<Integer>());
				results.get(tmp).add(i);
			}
		}
		
		Collection<LinkedList<Integer>> value = results.values();
		Iterator<LinkedList<Integer>> itv = value.iterator();
		String name;
		while(itv.hasNext()){
			Iterator<Integer> it = itv.next().iterator();
			while(it.hasNext()){
				name = nameTable.get(it.next());
				if(baseSet.contains(name)){
					System.out.print(name+"\t");
				}
			}
			System.out.println();
			System.out.println();
		}
	}
	
	public static void readFile(String f1, String f2, String f3, Map<Integer, String> nameTable, Set<String> baseSet) throws Exception{
		sim = new int[problemSize][problemSize];
		
		Scanner sc = new Scanner(new FileInputStream(f1));
		int i = 0, j = 0;
		while(sc.hasNext()){
			sim[i][j] = (int)(sc.nextFloat()*multiplier);
			j++;
			if(j == problemSize){
				j = 0;
				i++;
			}
		}
		
		String line;
		sc = new Scanner(new FileInputStream(f2));
		while(sc.hasNextLine()){
			line = sc.nextLine();
			String[] tmp = line.split(",");
			nameTable.put(Integer.parseInt(tmp[0]), tmp[1]);
		}
		
		sc = new Scanner(new FileInputStream(f3));
		while(sc.hasNextLine()){
			line = sc.nextLine();
			String[] tmp = line.split(",");
			baseSet.add(tmp[1]);
		}
	}
	
	public static void main(String[] argv) throws Exception{
		process();
	}
}
